|
In discrete geometry, a ''k''-set of a finite point set ''S'' in the Euclidean plane is a subset of ''k'' elements of ''S'' that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a ''k''-set of a finite point set is a subset of ''k'' elements that can be separated from the remaining points by a hyperplane. In particular, when ''k'' = ''n''/2 (where ''n'' is the size of ''S''), the line or hyperplane that separates a ''k''-set from the rest of ''S'' is a halving line or halving plane. ''K''-sets are related by projective duality to ''k''-levels in line arrangements; the ''k''-level in an arrangement of ''n'' lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly ''k'' lines below them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces.〔Agarwal et al. (1997); Chan (2003; 2005a,b).〕 == Combinatorial bounds == It is of importance in the analysis of geometric algorithms to bound the number of ''k''-sets of a planar point set,〔Chazelle and Preparata (1986); Cole et al. (1987); Edelsbrunner and Welzl (1986).〕 or equivalently the number of ''k''-levels of a planar line arrangement, a problem first studied by Lovász (1971) and Erdős et al. (1973). The best known upper bound for this problem is ''O''(''nk''1/3), as was shown by Tamal Dey (1998) using the crossing number inequality of Ajtai, Chvátal, Newborn, and Szemerédi. However, the best known lower bound is far from Dey's upper bound: it is Ω(''n'' exp(''c'' (log''k'')1/2)) for some constant ''c'', as shown by Toth (2001). In three dimensions, the best upper bound known is ''O''(''nk''3/2), and the best lower bound known is Ω(''nk'' exp(''c'' (log''k'')1/2)).〔Sharir et al. (2001).〕 For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of k-sets is Θ(''(n-k)k''), which follows from arguments used for bounding the complexity of k-th order Voronoi diagrams.〔Lee (1982); Clarkson and Shor (1989).〕 For the case when ''k'' = ''n''/2 (halving lines), the maximum number of combinatorially distinct lines through two points of ''S'' that bisect the remaining points when ''k'' = 1, 2, ... is :1,3,6,9,13,18,22... . Bounds have also been proven on the number of ≤''k''-sets, where a ≤''k''-set is a ''j''-set for some ''j'' ≤ ''k''. In two dimensions, the maximum number of ≤''k''-sets is exactly ''nk'',〔Alon and Győri (1986).〕 while in ''d'' dimensions the bound is .〔Clarkson and Shor (1989).〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-set (geometry)」の詳細全文を読む スポンサード リンク
|